package linked;

import btree.base.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Solution_437 {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 1);
        return dfs(root, 0, targetSum, map);
    }

    private int dfs(TreeNode node, long s, int targetNum, Map<Long, Integer> map) {
        if (node == null)
            return 0;
        s += node.val;
        int res = map.getOrDefault(s - targetNum, 0);
        map.merge(s, 1, Integer::sum);
        res += dfs(node.left, s, targetNum, map);
        res += dfs(node.right, s, targetNum, map);
        map.merge(s, -1, Integer::sum);

        return res;
    }
}
